package org.tissou.server.Utils;

import java.util.*;
import java.util.logging.Logger;

/**
 * Created by IntelliJ IDEA.
 * User: Manu
 * Date: 31 d�c. 2008
 * Time: 11:20:22
 * To change this template use File | Settings | File Templates.
 */
public class ComparateurApproximatif implements Comparator<String> {

  private static final Logger LOG = Logger.getLogger(ComparateurApproximatif.class.getName());

  private static final List<Character> ALPHABET;
  static {
    List<String> tmpAlphabet = Arrays.asList("a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.w.x.y.z".split("\\."));
    ALPHABET = new ArrayList<Character>(tmpAlphabet.size());
    for (String lettre : tmpAlphabet) {
      ALPHABET.add(lettre.charAt(0));
    }
  }

  public int compare(String s1, String s2) {
    s1 = compactString(s1);
    s2 = compactString(s2);
    if (s1.compareTo(s2) == 0) {
      return 0;
    } else if (s1.compareTo(s2) > 0) {
      return getEditDistance(s1, s2);
    } else {
      return - getEditDistance(s1, s2);
    }
  }

  private static String compactString(String string) {
    String input = string.toLowerCase();
    StringBuffer compactee = new StringBuffer();
    for (int i = 0; i < input.length(); i++) {
      char car = input.charAt(i);
      if (ALPHABET.contains(car)) {
        compactee.append(car);
      }
    }
    return compactee.toString();
  }

  private static int Minimum (int a, int b, int c) {
    int mi;
    mi = a;
    if (b < mi) {
      mi = b;
    }
    if (c < mi) {
      mi = c;
    }
    return mi;
  }

  public static int getEditDistance(String s, String t) {
    int d[][]; // matrix
    int n; // length of s
    int m; // length of t
    int i; // iterates through s
    int j; // iterates through t
    char s_i; // ith character of s
    char t_j; // jth character of t
    int cost; // cost

    // Step 1
    n = s.length ();
    m = t.length ();
    if (n == 0) {
      return m;
    }
    if (m == 0) {
      return n;
    }
    d = new int[n+1][m+1];

    // Step 2
    for (i = 0; i <= n; i++) {
      d[i][0] = i;
    }
    for (j = 0; j <= m; j++) {
      d[0][j] = j;
    }

    // Step 3
    for (i = 1; i <= n; i++) {
      s_i = s.charAt (i - 1);

      // Step 4
      for (j = 1; j <= m; j++) {
        t_j = t.charAt (j - 1);

        // Step 5
        if (s_i == t_j) {
          cost = 0;
        } else {
            cost = 1;
        }

        // Step 6
        d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
      }
    }

    return d[n][m];
  }
}
